import java.util.ArrayList;
import java.util.Collections;
/*
 * Created on Fri May 30 2025
 *
 * Author Alan
 * 
 * Implementation of Intensity Segment
 * 
 * @innerStore ArrayList of Segment,store data and malloc new space when space is used 
 * 
 * I user Mathematical Introduction to implement this Class
 * 
 */
public class IntensitySegments {
    private final ArrayList<Segment> innerStore = new ArrayList<Segment>();
    /**
     * inner class,if do not record end index,implementation will be subtle
     * and complex
     */
    public static class Segment{
        final int colsedStart;
        final int closedEnd;
        final int intensity;
        //[left,right),so inner storage just record right-1
        Segment(int start,int end,int intensity,boolean innerMergeFlag){
            this.colsedStart = start;
            if(innerMergeFlag){
                this.closedEnd = end;
            }else{
                this.closedEnd = end-1;
            }
            
            this.intensity = intensity;
        }
        
        public String toFullString(){
            return String.format("[%d,%d]:%d",this.colsedStart,this.closedEnd,this.intensity);
        }
        @Override
        public String toString(){
            return String.format("[%d,%d]",this.colsedStart,this.closedEnd+1);
        }
    }
    /**
     * @param from input segment start index
     * @param to input segment end index
     * @param amount record intensity
     */
    public void add(int from, int to, int amount) {
        if(to<from){
            throw new IllegalArgumentException(String.format("Illegal Parameter,from should less than to! current from:%d,to:%d\n",from,to));
        }
        Segment curSegment = new Segment(from, to, amount,false);
        //1. P(0) [from,to),left part is closed,right part is open
        if(innerStore.size()==0){
            innerStore.add(curSegment);
        }else{
            //2. P(n)->P(n++) find all overlap segment and merge
            ArrayList<Segment> overlapSegment = new ArrayList<Segment>();
            Segment segmentPtr = null;
            for(int i=0;i<innerStore.size();i++){
                segmentPtr = innerStore.get(i);
                /**
                 * overlap s1 segmentptr s2 cursegment
                 * 1.[s1 [s2 e2] e1]
                 * 2.[s2 [s1 e2] e1]
                 * 3.[s1 [s2 e1] e2]
                 * 4.[s2 [s1 s2] e2]
                 */
                //case 4
                if(segmentPtr.colsedStart>=curSegment.colsedStart && segmentPtr.closedEnd<=curSegment.closedEnd){
                    overlapSegment.add(segmentPtr);
                //case 1
                }else if(segmentPtr.colsedStart<=curSegment.colsedStart && segmentPtr.closedEnd>=curSegment.closedEnd){
                    overlapSegment.add(segmentPtr);
                //case 2 left non empty
                }else if(segmentPtr.colsedStart>curSegment.colsedStart&&segmentPtr.closedEnd>=curSegment.closedEnd
                && segmentPtr.colsedStart<=curSegment.closedEnd){
                    overlapSegment.add(segmentPtr);
                //case 3 right non empty
                }else if(segmentPtr.colsedStart<=curSegment.colsedStart&&segmentPtr.closedEnd<curSegment.closedEnd
                && segmentPtr.closedEnd>=curSegment.colsedStart){
                    overlapSegment.add(segmentPtr);
                }
            }
            //2.1 judge overlapsegment,if no affected segment,just  sort and insert
            if(overlapSegment.size()==0){
                innerStore.add(curSegment);
                qucikSort(innerStore,0,innerStore.size()-1);
            //2.2 deal merge    
            }else{
                innerStore.removeAll(overlapSegment);
                ArrayList<Segment> mergedSegments = dealMerge(overlapSegment,curSegment);
                innerStore.addAll(mergedSegments);
                qucikSort(innerStore, 0, innerStore.size()-1);
            }
        }  
    }
    /**
     * deal merge first split then consider merge
    *  overlap s1 segmentptr s2 cursegment
     * 1.[s1 [s2 e2] e1]
     * 2.[s2 [s1 e2] e1]
     * 3.[s1 [s2 e1] e2]
     * 4.[s2 [s1 s2] e2]
     * @param overlapSegments
     * @param curSegment
     * @return
     */
    public ArrayList<Segment> dealMerge(ArrayList<Segment> overlapSegments,Segment curSegment){
        ArrayList<Segment> mergedSegments = new ArrayList<>();
        Segment segmentPtr = null;
        //1. first split
        for(int i=0;i<overlapSegments.size();i++){
            segmentPtr = overlapSegments.get(i);
            //case 4
            if(segmentPtr.colsedStart>=curSegment.colsedStart && segmentPtr.closedEnd<=curSegment.closedEnd){
                mergedSegments.add(new Segment(segmentPtr.colsedStart,segmentPtr.closedEnd, segmentPtr.intensity+curSegment.intensity,true));
            //case 1 [s1 [s2 e2] e1]
            }else if(segmentPtr.colsedStart<=curSegment.colsedStart && segmentPtr.closedEnd>=curSegment.closedEnd){
                if(segmentPtr.colsedStart<curSegment.colsedStart){
                    mergedSegments.add(new Segment(segmentPtr.colsedStart,curSegment.colsedStart-1, segmentPtr.intensity,true));
                }
                mergedSegments.add(new Segment(curSegment.colsedStart,curSegment.closedEnd,segmentPtr.intensity+curSegment.intensity,true));
                if(segmentPtr.closedEnd>curSegment.closedEnd){
                    mergedSegments.add(new Segment(curSegment.closedEnd+1,segmentPtr.closedEnd,segmentPtr.intensity,true));
                }
            //case 2 [s2 [s1 e2] e1]
            }else if(segmentPtr.colsedStart>curSegment.colsedStart&&segmentPtr.closedEnd>=curSegment.closedEnd
            && segmentPtr.colsedStart<=curSegment.closedEnd){
                mergedSegments.add(new Segment(curSegment.colsedStart,segmentPtr.colsedStart-1, curSegment.intensity,true));
                mergedSegments.add(new Segment(segmentPtr.colsedStart,curSegment.closedEnd,segmentPtr.intensity+curSegment.intensity,true));
                if(segmentPtr.closedEnd>curSegment.closedEnd){
                    mergedSegments.add(new Segment(curSegment.closedEnd+1,segmentPtr.closedEnd,segmentPtr.intensity,true));
                }
            //case 3 [s1 [s2 e1] e2]
            }else if(segmentPtr.colsedStart<=curSegment.colsedStart&&segmentPtr.closedEnd<curSegment.closedEnd
            && segmentPtr.closedEnd>=curSegment.colsedStart){
                if(segmentPtr.colsedStart<curSegment.colsedStart){
                    mergedSegments.add(new Segment(segmentPtr.colsedStart,curSegment.colsedStart-1,segmentPtr.intensity,true));
                }
                mergedSegments.add(new Segment(curSegment.colsedStart,segmentPtr.closedEnd,segmentPtr.intensity+curSegment.intensity,true));
                mergedSegments.add(new Segment(segmentPtr.closedEnd+1,curSegment.closedEnd, curSegment.intensity,true));
            }
        }
        //2. consider merge
        ArrayList<Segment> mergedResult = new ArrayList<Segment>();
        Segment preSegment = null;
        Segment nowSegment = null;
        for(int i=0;i<mergedSegments.size();i++){
            if(preSegment==null){
                preSegment = mergedSegments.get(i);
            }else{
                nowSegment = mergedSegments.get(i);
                //2.1 merge judge
                if((preSegment.closedEnd==nowSegment.colsedStart-1)&&preSegment.intensity==nowSegment.intensity){
                    preSegment = new Segment(preSegment.colsedStart, nowSegment.closedEnd, preSegment.intensity,true);
                }else{
                    mergedResult.add(preSegment);
                    preSegment = nowSegment;
                    nowSegment = null;
                }
            }
        }
        if(preSegment!=null){
            mergedResult.add(preSegment);
        }
        return mergedResult;
    }
    /**
     * set range,like add implementation,but not update,just put
     * 1. get all affected Segment
     * 2. dealSet
     * @param from
     * @param to
     * @param amount
     */
    public void set(int from,int to,int amount) {
        if(to<from){
            throw new IllegalArgumentException(String.format("Illegal Parameter,from should less than to! current from:%d,to:%d\n",from,to));
        }
        Segment curSegment = new Segment(from, to, amount,false);
        //1. left part is closed,right part is open
        if(innerStore.size()==0){
            innerStore.add(curSegment);
        }else{
            //2. get all affected Segment
            ArrayList<Segment> overlapSegment = new ArrayList<Segment>();
            Segment segmentPtr = null;
            for(int i=0;i<innerStore.size();i++){
                segmentPtr = innerStore.get(i);
                /**
                 * overlap s1 segmentptr s2 cursegment
                 * 1.[s1 [s2 e2] e1]
                 * 2.[s2 [s1 e2] e1]
                 * 3.[s1 [s2 e1] e2]
                 * 4.[s2 [s1 s2] e2]
                 */
                //case 4
                if(segmentPtr.colsedStart>=curSegment.colsedStart && segmentPtr.closedEnd<=curSegment.closedEnd){
                    overlapSegment.add(segmentPtr);
                //case 1
                }else if(segmentPtr.colsedStart<=curSegment.colsedStart && segmentPtr.closedEnd>=curSegment.closedEnd){
                    overlapSegment.add(segmentPtr);
                //case 2 left non empty
                }else if(segmentPtr.colsedStart>curSegment.colsedStart&&segmentPtr.closedEnd>=curSegment.closedEnd
                && segmentPtr.colsedStart<=curSegment.closedEnd){
                    overlapSegment.add(segmentPtr);
                //case 3 right non empty
                }else if(segmentPtr.colsedStart<=curSegment.colsedStart&&segmentPtr.closedEnd<curSegment.closedEnd
                && segmentPtr.closedEnd>=curSegment.colsedStart){
                    overlapSegment.add(segmentPtr);
                }
            }
            //2.1 judge overlapsegment,if no affected segment,just  sort and insert
            if(overlapSegment.size()==0){
                innerStore.add(curSegment);
                qucikSort(innerStore,0,innerStore.size()-1);
            //2.2 deal merge    
            }else{
                innerStore.removeAll(overlapSegment);
                ArrayList<Segment> mergedSegments = dealPut(overlapSegment,curSegment);
                innerStore.addAll(mergedSegments);
                qucikSort(innerStore, 0, innerStore.size()-1);
            }
        }  
    }
    /**
     * deal put first split then consider merge
     * only  need to deal with curSegment-curSegment 
     *  overlap s1 segmentptr s2 cursegment
     * 1.[s1 [s2 e2] e1]
     * 2.[s2 [s1 e2] e1]
     * 3.[s1 [s2 e1] e2]
     * 4.[s2 [s1 s2] e2]
     * @param overlapSegments
     * @param curSegment
     * @return
     */
    public ArrayList<Segment> dealPut(ArrayList<Segment> overlapSegments,Segment curSegment){
        ArrayList<Segment> mergedSegments = new ArrayList<>();
        Segment segmentPtr = null;
        //1. first split
        for(int i=0;i<overlapSegments.size();i++){
            segmentPtr = overlapSegments.get(i);
            //case 4
            if(segmentPtr.colsedStart>=curSegment.colsedStart && segmentPtr.closedEnd<=curSegment.closedEnd){
                //do not need to deal,just add a huge Segment last
            //case 1 [s1 [s2 e2] e1]
            }else if(segmentPtr.colsedStart<=curSegment.colsedStart && segmentPtr.closedEnd>=curSegment.closedEnd){
                if(segmentPtr.colsedStart<curSegment.colsedStart){
                    mergedSegments.add(new Segment(segmentPtr.colsedStart,curSegment.colsedStart-1, segmentPtr.intensity,true));
                }
            //case 2 [s2 [s1 e2] e1]
            }else if(segmentPtr.colsedStart>curSegment.colsedStart&&segmentPtr.closedEnd>=curSegment.closedEnd
            && segmentPtr.colsedStart<=curSegment.closedEnd){
                if(segmentPtr.closedEnd>curSegment.closedEnd){
                    mergedSegments.add(new Segment(curSegment.closedEnd+1,segmentPtr.closedEnd,segmentPtr.intensity,true));
                }
            //case 3 [s1 [s2 e1] e2]
            }else if(segmentPtr.colsedStart<=curSegment.colsedStart&&segmentPtr.closedEnd<curSegment.closedEnd
            && segmentPtr.closedEnd>=curSegment.colsedStart){
                if(segmentPtr.colsedStart<curSegment.colsedStart){
                    mergedSegments.add(new Segment(segmentPtr.colsedStart,curSegment.colsedStart-1,segmentPtr.intensity,true));
                }
            }
        }
        /**
         * add curSegment in last,then take a sort for next merge
         */
        mergedSegments.add(curSegment);
        qucikSort(mergedSegments, 0, mergedSegments.size()-1);
        //2. consider merge
        ArrayList<Segment> mergedResult = new ArrayList<Segment>();
        Segment preSegment = null;
        Segment nowSegment = null;
        for(int i=0;i<mergedSegments.size();i++){
            if(preSegment==null){
                preSegment = mergedSegments.get(i);
            }else{
                nowSegment = mergedSegments.get(i);
                //2.1 merge judge
                if((preSegment.closedEnd==nowSegment.colsedStart-1)&&preSegment.intensity==nowSegment.intensity){
                    preSegment = new Segment(preSegment.colsedStart, nowSegment.closedEnd, preSegment.intensity,true);
                }else{
                    mergedResult.add(preSegment);
                    preSegment = nowSegment;
                    nowSegment = null;
                }
            }
        }
        if(preSegment!=null){
            mergedResult.add(preSegment);
        }
        return mergedResult;
    }

    /**
     * output as string
     */
    @Override
    public String toString(){
        StringBuilder sBuilder = new StringBuilder();
        sBuilder.append("[");
        boolean firstFlag = true;
        Segment curSegment = null;
        Segment nexSegment = null;
        for(int i=0;i<innerStore.size();i++){
            if(!firstFlag){
                sBuilder.append(",");
            }else{
                firstFlag = false;
            }
            curSegment = innerStore.get(i);
            if(i+1<innerStore.size()){
                nexSegment = innerStore.get(i+1);
            }
            if(nexSegment!=null){
                if(curSegment.closedEnd==nexSegment.colsedStart-1){
                    sBuilder.append(String.format("[%d,%d]",curSegment.colsedStart,curSegment.intensity));
                }else{
                    sBuilder.append(String.format("[%d,%d],[%d,%d]",curSegment.colsedStart,
                    curSegment.intensity,curSegment.closedEnd+1,0));
                }
            }else{
                sBuilder.append(String.format("[%d,%d],[%d,%d]",curSegment.colsedStart,
                curSegment.intensity,curSegment.closedEnd+1,0));
            }
            //System.out.printf("经过%d步骤后，当前单位:%s，结果:%s\n",i,innerStore.get(i),sBuilder.toString());
        }
        sBuilder.append("]");
        //System.out.println("------------------------------");
        return sBuilder.toString();
    }
    /**
     * quicksort implementation
     * @param segements
     * @param low
     * @param high
     */
    public void qucikSort(ArrayList<Segment> segements,int low,int high){
        if(low>high){
            return;
        }
        int partition = findPartition(segements,low,high);
        qucikSort(segements, low, partition-1);
        qucikSort(segements, partition+1, high);
    }
    /**
     * quicksort findPartition
     * @param segements
     * @param low
     * @param high
     * @return
     */
    public int findPartition(ArrayList<Segment> segements,int low,int high){
        int pivortalIndex = low;
        int lIndex = low;
        int rIndex = high;
        while(lIndex<rIndex){
            while(lIndex<rIndex){
                if(!greaterThan(segements, pivortalIndex, rIndex)){
                    Collections.swap(segements,pivortalIndex,rIndex);
                    pivortalIndex = rIndex;
                    lIndex++;
                }else{
                    rIndex--;
                }
            }
            while(lIndex<rIndex){
                if(!greaterThan(segements, lIndex, pivortalIndex)){
                    Collections.swap(segements,lIndex,pivortalIndex);
                    rIndex--;
                }else{
                    lIndex++;
                }
            }
        }
        return low;
    }
    /**
     * sort customize
     * @param segements
     * @param lIndex
     * @param rIndex
     * @return
     */
    public boolean greaterThan(ArrayList<Segment> segements,int lIndex,int rIndex){
        return segements.get(lIndex).colsedStart<segements.get(rIndex).colsedStart?true:false;
    }
    /**
     * getInnerStorage,utils for TestClass
     * @return
     */
    public ArrayList<Segment> getSegments(){
        return this.innerStore;
    }
}
